package Hot100.Medium.GreedyAndDP.DynamicPlanning;

public class LC70_ClimbStairs {
    public static void main(String[] args) {

    }

    public int climbStairs(int n){
        // dp数组含义是到达dp[i]阶梯有几种办法
        int[] dp = new int[n + 1];
        // 第一层阶梯就一个办法，第二层两个，1+1或者直接跳两层
        dp[1] = 1;
        dp[2] = 2;
        // 递推公式：由于每层向后都是跳一节或者两节，那相当于dp[i]可以由dp[i - 2]跳两层得到也可以由dp[i - 1]跳一层得到
        for(int i = 3; i <= n; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    // 用变量记录代替数组，优化空间复杂度
    public int climbStairs2(int n) {
        if(n <= 2) return n;
        int a = 1, b = 2, sum = 0;

        for(int i = 3; i <= n; i++){
            sum = a + b;  // f(i - 1) + f(i - 2)
            a = b;        // 记录f(i - 1)，即下一轮的f(i - 2)
            b = sum;      // 记录f(i)，即下一轮的f(i - 1)
        }
        return b;
    }
}
